﻿/******************************************************************************
 * 
 * Announce: CSharpKit, Basic algorithms, components and definitions.
 *           Copyright (C) ShenYongchen.
 *           All rights reserved.
 *   Author: 申永辰.郑州 (shenyczz@163.com)
 *  WebSite: http://github.com/shenyczz/CSharpKit
 *
 * THIS CODE IS LICENSED UNDER THE MIT LICENSE (MIT).
 * THIS CODE IS PROVIDED *AS IS* WITHOUT WARRANTY OF 
 * ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING ANY
 * IMPLIED WARRANTIES OF FITNESS FOR A PARTICULAR
 * PURPOSE, MERCHANTABILITY, OR NON-INFRINGEMENT.
 * 
******************************************************************************/
using System;

namespace CSharpKit.Numerics.Theories
{
    /// <summary>
    /// 排列
    /// </summary>
    [Serializable]
    public class Permutation
    {
        #region Constructor

        /// <summary>
        /// 构造排列实例
        /// </summary>
        /// <param name="indices">
        /// 表示每个整数排列的位置的数组：
        /// An array which represents where each integer is permuted too:
        /// indices[i] represents that integer i is permuted to location indices[i].
        /// </param>
        public Permutation(int[] indices)
        {
            if (!CheckForProperPermutation(indices))
            {
                throw new ArgumentException(Resources.Numerics.PermutationAsIntArrayInvalid, nameof(indices));
            }

            _indices = new int[indices.Length];
            Array.Copy(indices, _indices, indices.Length);
        }

        #endregion

        #region Fields

        /// <summary>
        /// 表示i被排列的位置
        /// </summary>
        private readonly int[] _indices;

        #endregion

        /// <summary>
        /// 维度
        /// </summary>
        public int Dimension => _indices.Length;


        /// <summary>
        /// Computes where <paramref name="idx"/> permutes too.
        /// </summary>
        /// <param name="idx">The index to permute from.</param>
        /// <returns>The index which is permuted to.</returns>
        public int this[int idx] => _indices[idx];

        /// <summary>
        /// 排列的逆 ?（？和原排列一样？） 排列的倒数
        /// </summary>
        /// <returns>The inverse of the permutation.</returns>
        public Permutation Inverse()
        {
            var invIdx = new int[Dimension];

            for (int i = 0; i < invIdx.Length; i++)
            {
                invIdx[_indices[i]] = i;
            }

            return new Permutation(invIdx);
        }

        /// <summary>
        /// Construct an array from a sequence of inversions.
        /// 从一个反转序列构造一个数组
        /// </summary>
        /// <example>
        /// From wikipedia: the permutation 12043 has the inversions (0,2), (1,2) and (3,4). This would be
        /// encoded using the array [22244].
        /// </example>
        /// <param name="inv">The set of inversions to construct the permutation from.</param>
        /// <returns>A permutation generated from a sequence of inversions.</returns>
        public static Permutation FromInversions(int[] inv)
        {
            var idx = new int[inv.Length];
            for (int i = 0; i < inv.Length; i++)
            {
                idx[i] = i;
            }

            for (int i = inv.Length - 1; i >= 0; i--)
            {
                if (idx[i] != inv[i])
                {
                    int t = idx[i];
                    idx[i] = idx[inv[i]];
                    idx[inv[i]] = t;
                }
            }

            return new Permutation(idx);
        }

        /// <summary>
        /// 从排列中构造一个反转序列
        /// </summary>
        /// <example>
        /// From wikipedia: the permutation 12043 has the inversions (0,2), (1,2) and (3,4). This would be
        /// encoded using the array [22244].
        /// </example>
        /// <returns>A sequence of inversions.</returns>
        public int[] ToInversions()
        {
            var idx = (int[])_indices.Clone();

            for (int i = 0; i < idx.Length; i++)
            {
                if (idx[i] != i)
                {
                    int q = Array.FindIndex(idx, i + 1, x => x == i);
                    var t = idx[i];
                    idx[i] = q;
                    idx[q] = t;
                }
            }

            return idx;
        }

        /// <summary>
        /// 功能：检查数组是否是一个正确的排列<para/>
        /// </summary>
        /// <param name="indices">整数数组：indices[i] 的值表示整数 i 的排列位置。</param>
        /// <remarks>
        /// 1. 数组中的数值是自然数（大于等于0的整数）<para/>
        /// 2. 数组中的数值小于数组长度（保证是从0开始且级差等于1的的整数：0，1，2，3，4，5，6，...）<para/>
        /// </remarks>
        /// <returns>true or false</returns>
        public static bool CheckForProperPermutation(int[] indices)
        {
            var idxCheck = new bool[indices.Length];

            for (int i = 0; i < indices.Length; i++)
            {
                // if (indices[i] < 0 || indices[i] >= indices.Length)
                // {
                //     return false;
                // }
                // idxCheck[indices[i]] = true;

                idxCheck[indices[i]] = true
                    && indices[i] >= 0              // 数组中的数值是自然数(>=0)
                    && indices[i] < indices.Length; // 数组中的数值小于数组长度(从0开始且级差等于1的的整数)
            }

            for (int i = 0; i < indices.Length; i++)
            {
                if (idxCheck[i] == false)
                {
                    return false;
                }
            }

            return true;
        }


        //}}@@@
    }


}
